Digital video techniques have found widespread applications in various aspects of the society, such as telecommunication, broadcast, and entertainment. Video coding is to compress digital video information so that more efficient transmission and storage may be achieved. Video coding is a core multimedia technology, and video compression coding standards are the basis of the digital media industry. H.264/AVC (MPEG4-Part10) is a new generation of video coding standards jointly developed by ITU-T VCEG (Video Coding Experts Group) and ISO/IEC MPEG JVT (Joint Video Team). Additionally, other examples of video coding standards may include AVS1.0-P2 developed by VC-1 (previously known as WMV-9) and AVS (Audio Video Standard) or the like.
The basic framework for MPEG/JVT/VCEG video coding standards is to employ a hybrid coding framework incorporating block-based motion compensation and transform coding, including intra-frame prediction, inter-frame prediction, transformation, quantization, entropy coding, and so on. For inter-frame prediction, block-based motion vectors are used to eliminate redundancy among images. For intra-frame prediction, spatial prediction modes are used to eliminate redundancy within an image. Then, prediction residual is subject to transformation and quantization, to eliminate visual redundancy within the image. Finally, entropy coding is applied to the motion vectors, prediction modes, quantization parameters and transformation coefficients for compression. During video decoding, the basic processing unit is macro block. A macro block has a luminance block of 16×16 pixels and a corresponding chroma block. A macro block may be divided into blocks, and the size of a block may be 16×8, 8×16, 8×8, 8×4, 4×8, 4×4 or the like. A block is usually subject to intra-frame, inter-frame predictions and transformation.
A motion vector (MV) is the output of a motion estimation operation during inter-frame prediction in video coding, and equals the coordinate offset of the current block relative to a matching reference block in the image, including horizontal MV and vertical MV. Motion estimation may comprise integer-pixel motion estimation and sub-pixel motion estimation. Sub-pixel may include ½ pixel and ¼ pixel. Motion estimation is performed in units of minimum sub-pixels, such as ¼ pixel, and thus motion vector is an integer constantly. To enable a more efficient compression, prediction processing is further performed on motion vectors. Prediction processing on motion vectors is usually based on motion vectors of adjacent blocks. A prediction value is referred to as MVD (Motion Vector Difference), including horizontal MVD and vertical MVD. The unit of MVD is same as that of MV, and is also minimum sub-pixel, such as ¼ pixel. Thus, MVD is also an integer constantly. Accordingly, the MVD absolute value is a nonnegative integer.
In the framework of video compression, the transformed and quantized residual coefficients and MVDs are processed at the entropy coder, to eliminate statistical redundancy among data, and then outputted into a code stream.
The entropy coder may comprise a Huffman coder or an arithmetic coder. The two coders are widely used in standards such as H.264/AVC and AVS1.0-P2. The Huffman coder maps symbols with different probabilities to binary bit strings of different lengths through variable length coding, so as to remove statistical redundancy. The arithmetic coder removes statistical redundancy by mapping a symbol sequence to a numeral within an interval of [0, 1).
Currently used arithmetic coders mainly include Binary Arithmetic Coders (BAC), for example, Q-Coder (a binary arithmetic coder), QM-Coder (a binary arithmetic coder), MQ-Coder (a binary arithmetic coder), and CABAC (Context based Adaptive Binary Arithmetic Coder) in H.264/AVC. Each BAC has a binary bit string as its input. Recursive division of the interval may be implemented according to the probabilities of symbols (0, 1) in the bit string. Ultimately, the entire bit string is mapped to a code stream.
Because a BAC has a binary bit string as its input as shown in FIG. 1, the coded data first needs to be binarized in video compression standards (for example, H.264/AVC standard). That is, the symbols to be coded (i.e., non binary data, such as the transformed and quantized coefficients or MVD absolute values) are mapped to a binary string. Binarization is a pre-process before binary arithmetic coding is performed. In the present invention, binarization is also referred to as binary coding, which means assigning a binary codeword to a symbol.
Currently, many methods may be used for binarization, for example, fixed length code, unary code, exp-Golomb and etc. Descriptions are made below to various coding processes.
(1) Fixed Length Code
A fixed length code has a fixed codeword length. In this way, a symbol set corresponding to a fixed length code has a limited number of symbols, with the number of symbols determined by the length of the fixed length code. Typically, a fixed length code of length N may represent 2N symbols. Taking 8 symbols as an example, the length of the fixed length code is 3, specifically as shown in Table 1.
TABLE 1SymbolCodeword00001001201030114100510161107 111.
(2) Unary Code
The unary code represents a symbol as a run of 1's (or 0's) and a tail 0 (or 1). The number of 1's (or 0's) in the run is equal to the value of the symbol. Unary code is very simple. However, when the value of the symbol is rather large, a long codeword string will occur, as shown in Table 2.
TABLE 2SymbolCodeword00110211031110411110511111061111110711111110. . .
Truncated unary code is a special form of unary code. Unary code may represent an infinite number of codewords. However, when there is a finite number of coedwords, the last-bit terminator for the last codeword is redundant and thus may be removed. Such a codeword is referred to as truncated unary code. Specifically, when the number of codwords is N+1, the (N+1)th codeword is set as a run of N 1's (or 0's) and the terminator 0 (or 1) is omitted, to form a N-bit truncated unary code. As shown in Table 2, the codeword of symbol “7” is modified to be “1111111”, that is, to have 7-bit truncated unary code.
(3) Oder k Exp-Golomb Code
The exp-Golomb code has a prefix portion and a postfix portion. The number of codewords grows exponentially as the code length increases. For order k exp-Golomb code, its prefix portion has a run of 0's and a 1. The number of 0's in the longest run read from the leftmost bit in the prefix is counted as LeadingZeroBits. In this way, the bit number of the postfix portion is determined as LeadingZeroBits+k. From the read bit number of the postfix, bits(LeadingZeroBits+k) may be determined through parsing. For parsing an order k exp-Golomb code, the codeword may be calculated as CodeNum=2LeadingZeroBits+k−2k+bits(LeadingZeroBits+k). Table 3 lists exp-Golomb codewords when k=0, 1, 2, or 3.
TABLE 3Order k exp-Golomb code tableThe Range ofOrderCodeword StructureCodeNumk = 0100 1 x01~20 0 1 x1 x03~60 0 0 1 x2 x1 x0 7~14. . .. . .k = 11 x00~10 1 x1 x02~50 0 1 x2 x1 x0 6~130 0 0 1 x3 x2 x1 x014~29. . .. . .k = 21 x1 x00~30 1 x2 x1 x0 4~110 0 1 x3 x2 x1 x012~270 0 0 1 x4 x3 x2 x1 x028~59. . .. . .k = 31 x2 x1 x00~70 1 x3 x2 x1 x0 8~230 0 1 x4 x3 x2 x1 x024~550 0 0 1 x5 x4 x3 x2 x1 x0 56~119. . .. . .
When the above order k exp-Golomb codes are parsed, a search is made first from the current position of the bit stream until the first non-zero bit is found, and the number of zeros found in this process is accumulated as leadingZeroBits. Then, CodeNum may be calculated from leadingZeroBits. The corresponding pseudo code is described as follows.
leadingZeroBits = −1;for ( b = 0; ! b; leadingZeroBits++ ) b = read_bits(1)CodeNum = 2leadingZeroBits + k − 2k + read_bits(leadingZeroBits + k).
The first form of order k exp-Golomb code is described as above. The order k exp-Golomb code may have a second form. For the order k exp-Golomb code of this second form, the prefix portion has a run of 1's and a 0. The number of 1's in the longest run read from the leftmost bit of the prefix is counted as LeadingBits. In this way, the bit number of the postfix portion is determined as LeadingBits+k. From the read bit number of the postfix, bits(LeadingBits+k) may be determined through parsing. For parsing a order k exp-Golomb code, the codeword may be calculated as CodeNum=2LeadingBits+k−2k+bits(LeadingBits+k). Table 4 lists exp-Golomb codewords of this form when k=0, 1, 2, or 3.
TABLE 4The Range ofOrderCodeword StructureCodeNumk = 0001 0 x01~21 1 0 x1 x03~61 1 1 0 x2 x1 x0 7~14. . .. . .k = 10 x00~11 0 x1 x02~51 1 0 x2 x1 x0 6~131 1 1 0 x3 x2 x1 x014~29. . .. . .k = 20 x1 x00~31 0 x2 x1 x0 4~111 1 0 x3 x2 x1 x012~271 1 1 0 x4 x3 x2 x1 x028~59. . .. . .k = 30 x2 x1 x00~71 0 x3 x2 x1 x0 8~231 1 0 x4 x3 x2 x1 x024~551 1 1 0 x5 x4 x3 x2 x1 x0 56~119. . .. . .
When the above order k exp-Golomb codes are parsed, a search is made first from the current position of the bit stream until the first “0” bit is found, and the number of “1” bits found in this process is accumulated as leadingBits. Then, CodeNum may be calculated from leadingBits. The corresponding pseudo code is described as follows.
leadingBits = −1;for ( b = 1; ! b; leadingBits++ ) b = read_bits(1)CodeNum = 2leadingBits + k − 2k + read_bits(leadingBits + k).
From the specific implementations of the above various binary coding methods, it can be seen that each binary coding method has its limitations in practical applications. That is, they cannot provide appropriate binary coding by adapting to the distribution properties of various sources flexibly, which influences the coding performance to some extent.